import java.util.Arrays;


public class MemoryManagementSystem {
	private String[] secondaryMemory;	//This array will hold the secondary memory
	private boolean useLRU; 				// true if LRU is used, false if FIFO is used
	private dLinkedList mainMemory;
	private link[] index=new link[1000];
	
	private class dLinkedList{
		public link first;
		public link last;
		private int length;
		public dLinkedList()
		{
			first=null;
			last=null;
			length=0;
		}
		public void enqueue(int page,String data)
		{
				if(last==null)
				{
					first = new link(null,null,page,data);
					last = first;
					this.length++;
				}
				else
				{
					last.after = new link(last,null,page,data);
					last.after.before=last;
					last=last.after;
					if(this.length==50)
						dequeue();
					else
						this.length++;
						
				}
				
			
		}
		public void dequeue()
		{
			secondaryMemory[first.pageIndex]=first.data;
			first=first.after;
			first.before=null;
		}
	}
		private class link {
			public link before;
			public link after;
			public int pageIndex;
			public String data;
			public link(link before, link after,int page,String data)
			{
				this.before=before;
				this.after=after;
				pageIndex=page;
				this.data=data;
			}
			
		}
	
	public MemoryManagementSystem(boolean useLRU) {
		secondaryMemory = new String[1000];
		for(int i=0;i<secondaryMemory.length;i++)
		{
			secondaryMemory[i]="";
			index[i]=null;
		}
		this.useLRU = useLRU;
		mainMemory= new dLinkedList();
		for(int i=0;i<50;i++)
		{
			mainMemory.enqueue(i, secondaryMemory[i]);
			index[i]=mainMemory.last;
		}
		
	}

	/*
	 * (non-Javadoc)
	 * @see java.lang.Object#toString()
	 */
	public String toString() {
		
		System.out.println( "secondaryMemory=" +Arrays.toString(secondaryMemory));
		return "secondaryMemory=" + Arrays.toString(secondaryMemory);
	}
	
	//This method returns the data you read. Notice that this data is not used by our main, but you can use it for testing your code.
	public String read(int index) {
		if(this.index[index]==null)
			load(index);
		if(useLRU)
			Rearange(index);
		return this.index[index].data;
	}
	private void Rearange(int index)
	{
		if(this.index[index]!=mainMemory.last && this.index[index]!=mainMemory.first)
		{
			this.index[index].before.after=this.index[index].after.before;
			this.index[index].after.before=this.index[index].before.after;
			this.index[index].after=null;
			this.index[index].before=mainMemory.last;
			mainMemory.last.after=this.index[index];
			mainMemory.last=this.index[index];
		}
		else
		{
			if(this.index[index]==mainMemory.first)
			{
				mainMemory.first.before=mainMemory.last;
				mainMemory.last=mainMemory.first;
				mainMemory.first.after=mainMemory.first;
				mainMemory.first=mainMemory.last;
				mainMemory.first.after=mainMemory.last.after;
				mainMemory.last.after=null;
				mainMemory.first.before=null;
			}
		}
	}
	
	public void write(int index, char c) {
		if(this.index[index]==null)
			load(index);
		if(useLRU)
			Rearange(index);
		this.index[index].data=this.index[index].data.toString()+c;
	}
	
	private void load(int index)
	{
		mainMemory.enqueue(index, secondaryMemory[index]);
		this.index[index]=mainMemory.last;
	}
}
